//CQOI2007
#include <stdio.h>
#include <string.h>
#define M 102
char str[M],str2[M];
int dp[M][M], dp2[M];
int min(int a, int b) {
	return a<b?a:b;
}
int main() {
	memset(dp,127,sizeof(dp));
	memset(dp2,127,sizeof(dp2));
	dp2[0]=0;
	
	int n,i,j,k;
	scanf("%s%s", str2+1, str+1);
	n=strlen(str+1);
	for(i = 1; i <= n; i ++)
		for(j = 1; i + j-1 <= n; j ++) {
			if(i == 1)
				dp[j][i+j-1]=1;
			else if(str[j]==str[i+j-1])
				dp[j][i+j-1]=min(dp[j+1][i+j-1],dp[j][i+j-2]);
			else for(k = j; k < i + j - 1; k ++) 
				dp[j][i+j-1]=min(dp[j][i+j-1],dp[j][k]+dp[k+1][i+j-1]);
			//printf("%d %d %d %d\n",dp[j][i+j-1],j,i+j-1,n);
		}
			
	for(i = 1; i <= n; i ++) {
		if(str2[i]==str[i])
			dp2[i]=dp2[i-1];
		else
			for(j = 0; j < i; j ++)
				dp2[i]=min(dp2[i],dp2[j]+dp[j+1][i]);
	}
	printf("%d",dp2[n]);
	return 0;
}
